package fun.coding.leetcode;

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringWithoutRepeatingChars {

    public static void main(String[] args) {
        LongestSubstringWithoutRepeatingChars lswr = new LongestSubstringWithoutRepeatingChars();
        // String s = "abcabcbb";
        //String s = "aaaaaaa";
        // String s = "aaabcdbefg";
        // String s = "xyzabcdbefdghijklmn";
        String s = "wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco";
        
        System.out.println("longest is " + lswr.lengthOfLongestSubstring(s));
    }
    
    public int lengthOfLongestSubstring(String s) {
    	if (s == null || s.length() == 0) return 0;
        // TODO: A hashmap could be optimized using an char array [128] if it is all ASCII, or use 256 since extended ASCII is 256
        HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();
        
        int max = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
        	char c = s.charAt(i);
        	// Need to be >= 
        	if (lookup.containsKey(c) && lookup.get(c) >= start) {
        		start = lookup.get(c) + 1;
        	}
        	
        	lookup.put(c, i);
        	max = Math.max(max, i - start + 1);
        }
        
        return max;
    }
    
    // first, 'a' and 'A' same or different, i think different. 
    // Kinda keep a sliding window
    // First, use hashmap or hashset, then can talk about optimize to bitset
    // The idea here is to use two pointers, i and j, j keeps increasing until reaching the end while i can leap when 
    // there is a dup char. Remember to update the hashmap to remove all the dups between the i and j. 
    // Further optimization could be use a int[256] to replace the hashmap if it is all ASCII, unicode cann't be done this way
    // since there are too many unicode chars. 
    public int lengthOfLongestSubstringOld(String s) {
        if (s == null || s.length() == 0) return 0;
        
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int maxLength = 0;
        
        int i = 0;
        int j = i + 1;
        while (i < s.length() && j < s.length()) {
            map.put(s.charAt(i), i);
            
            while (j < s.length()) {
                if (!map.containsKey(s.charAt(j))) {
                    map.put(s.charAt(j), j);
                } else {
                    maxLength = Math.max(maxLength, j - i);
                    
                    int pre = map.get(s.charAt(j));
                    // Delete all the nodes in between since we have discarded them
                    // Could do it without deleting while only compare the index, if index is less than start, 
                    // meaning this is discarded 
                    for (int k = i; k <= pre; k++) {
                        map.remove(s.charAt(k));
                    }
                    map.put(s.charAt(j), j);
                    // The new counting point
                    i = pre + 1;
                }
                j++;
            }
        }
        
        maxLength = Math.max(maxLength, j - i);
        
        return maxLength;
    }

}
